package seqList.LeetCode;
//LeetCode 剑指OfferII 第21题  删除链表的倒数第n个节点

public class OfferII_21 {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //判断链表是否为空或者只有一个节点
        if(head == null || head.next == null){
            return null;
        }
        //链表至少拥有两个节点
        //使用虚拟节点可以保证让low走到low的前驱，直接变成n+1的话会增加其他的情况
        ListNode dummyHead = new ListNode(9999);
        dummyHead.next = head;
        ListNode fast = dummyHead.next;
        ListNode low = dummyHead;

        //让fast先往后走n步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        //一起遍历
        while (fast != null){
            low = low.next;
            fast = fast.next;
        }
        low.next = low.next.next;
        return dummyHead.next;
    }
}
